home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 6567 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  1.9 KB
  1. Path: news.microsoft.com!news
  2. From: a-cnadc@microsoft.com (Dann Corbit)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: Finding a prime number
  5. Date: 19 Feb 1996 18:36:37 GMT
  6. Organization: Microsoft Corporation
  7. Message-ID: <4gafvl$23k@news.microsoft.com>
  8. References: <DMpuHt.3yL@cwi.nl> <4fl2tl$ln6@ns2.emirates.net.ae> <4fnnfuINNib7@keats.ugrad.cs.ubc.ca> <4fp2kt$pks@oban.cc.ic.ac.uk <1996Feb14.070305.19468@lafn.org>
  9. NNTP-Posting-Host: 157.57.171.202
  10. Mime-Version: 1.0
  11. X-Newsreader: WinVN 0.93.14
  12.  
  13. In article <1996Feb14.070305.19468@lafn.org>, an234@lafn.org says...
  14. >
  15. >
  16. >In a previous article, dik@cwi.nl (Dik T. Winter) says:
  17. >
  18. >>In article <4fp2kt$pks@oban.cc.ic.ac.uk> a.kruczkowski@ic.ac.uk (Alex Kruczkowski) writes:
  19. >> > Any comments or am I way off here? ;-)
  20. >>
  21. >>Way off I think.  There is no repeating pattern in the list of prime
  22. >>numbers.
  23. >>-- 
  24. >>dik t. winter, cwi, kruislaan 413, 1098 sj  amsterdam, nederland, +31205924098
  25. >>home: bovenover 215, 1025 jn  amsterdam, nederland; http://www.cwi.nl/~dik/
  26. >>
  27. >Ok... Here is some code
  28. >
  29. >#include <stdio.h>
  30. >#include <conio.h>
  31. >
  32. >int is_prime(int n)
  33. >//return 0 if not prime 
  34. >//return 1 if prime
  35. >{
  36. >        int i,temp=0;
  37. >        for(i=2; i==n-1, n%i!=0; i++)
  38. >          {
  39. >          }
  40. >        /* If i==n or n ==1 then n is prime */
  41. >        if (i==n || n==1) temp = 1;
  42. >        return(temp);
  43. >}
  44. >
  45. >I think this works pretty well.  I however don't know how fast it is..
  46.  
  47. A quick speedup can be made by only testing up to sqrt(n), since if
  48. n has any factors, at least one of them is <= sqrt(n).  For most cases
  49. that will make this routine run MUCH faster.  A sequential list of
  50. primes will also reduce the work, since all numbers can be expressed
  51. as a unique factorization of primes.  Testing with composites wastes
  52. effort.
  53. -- 
  54. The opinions expressed in this message are my own personal views 
  55. and do not reflect the official views of Microsoft Corporation.
  56.  
  57.